The present invention relates generally to computing systems and in particular to a method of managing an event queue or buffer that is asynchronously accessed and managed by at least two different, unsynchronized elements.
In data processing activity it is often necessary to temporarily store data items in time-ordered fashion so that those earlier stored can be retrieved first. One method of such storage is a queue: a data structure that stores data elements that are usually retrieved in the same order they are received, i.e., a data structure that operates in accordance with a first-in-first-out (FIFO) constraint. (Other types of queues may base retrieval of data items on factors other than when stored.)
While queue operation, use, and management is relatively simple in the context of a single application/processor, queue management can become more difficult in operating environments in which there exist multiple processing units and/or processes needing access to a single queue. Typically, to ensure that the queue is not changed by a second processing unit or process while being accessed by a first processing unit or process, a lock will be established by the first processing unit/process to preclude access while it is changing or accessing the queue. In a multiple process environment (e.g., a multiple thread system) this method of ensuring queue consistency can seriously affect system efficiency. This is an especially acute problem when the threads are running as a user mode process. For example, suppose a thread seeks to access a queue, locking it to ensure it is not changed before it is through. But, before the thread can complete its use of the queue, it is preempted (i.e., its time slice has expired), and it must wait until it can again operate. Until then, the queue cannot be accessed by any other thread, process or processor.
Also, suppose the queue is used by two processing elements, one to add data elements to the queue, and another to retrieve those data elements. The queue pointers, the address information that identifies where in the queue the next data item is to be stored, or the location of the data item next in line for retrieval, must be separately managed.
Typically, one unit, for example the unit removing or pulling data from the queue, must read (or have written to it) the queue pointer of the other unit adding or pushing data onto the queue so that the two pointers can be compared to determine if the queue is empty or contains data to be pulled (removed). This separate read or write has a negative impact on performance.